/**
 * Contains methods to solve a Sudoku puzzle
 * 
 * Strategies:
 * 		ForceMove: If there is an unresolved cell with only one possible option place it
 * 		Elimination: If there is only one unresolved cell in a row (column, box) where a certain value can be placed, place it there
 * 		PairElimination: If two cells in a row (column, box) have two candidates a and b, 
 * 							a and b can be removed from all other positions in the row (column, box)
 * 		colBox & rowBox: if a value only occurs in one box in a column (row), eliminate the value from the other columns (row) in the box
 * 
 * @author Theresa Wellington
 * @date April 2013
 *
 */
public class SudokuSolver {
	private Board sudokuBoard;
	
	public SudokuSolver(Board sudokuBoard){
		this.sudokuBoard = sudokuBoard;
	}
	
	public boolean isSolved(){
		return sudokuBoard.isSolved();
	}
	
	/**
	 * 
	 * @return a string representing the solution if solved, or the possibilities for each board cell if not
	 */
	public String printBoard(){
		if(sudokuBoard.isSolved()){
			return sudokuBoard.printBoard();
		}
		else return sudokuBoard.printBoardPossibles();
	}
	

	/**
	 * Calls tryToSolve; will attempt tryToSolve a maximum of 5 times
	 * @return true if puzzle is solved, false otherwise
	 */
	public boolean solve(){
		int tryToSolveCount = 0;
		while(tryToSolveCount<5 && !isSolved()){
			tryToSolve();
			tryToSolveCount++;
		}
		return isSolved();
	}
	
	/**
	 * attempts the methods specified at the top of the document
	 */
	private void tryToSolve(){
		boolean forceMove = true;
		while(forceMove){
			forceMove = forceMove();
		}
		if(isSolved()) return;
		
		//while elimination returns true, keep trying
		boolean elimination = true;
		while(elimination){
			elimination = elimination();
		}
		if(isSolved()) return;
		
		//forceMove again
		forceMove= true;
		while(forceMove){
			forceMove = forceMove();
		}
		if(isSolved()) return;
		
		//try pairElim -- can't do whilePairElim true because it will enter infinite loop
		pairElimination();
		if(isSolved()) return;
		
		//try rowBox -- can't do while rowBox true because it will enter infinite loop
		rowBox();
		if(isSolved()) return;
		
		//try colBox -- can't do while colBox true because it will enter infinite loop
		colBox();
	}
	
	/**
	 * If there is an unresolved cell with only one possible option place it
	 * @return true if a cell was forceMoved, false otherwise
	 */
	private boolean forceMove(){
		int placed = 0;
		
		for (int row = 0; row<sudokuBoard.getBoardSize(); row++){
			for (int col =0; col<sudokuBoard.getBoardSize(); col++){
				Cell currentCell = sudokuBoard.getCell(row,col);
				//if the cell is unsolved and there is only one possible value for the cell, place it
				if(!currentCell.isSolved() && currentCell.getPossibleValuesCount()==1){
					sudokuBoard.placeCell(currentCell, row, col, currentCell.getSinglePossibleValue());
					placed+=1;
				}
			}
		}
		if(placed!=0){
			return true;
		}
		else{
			return false;
		}
	}
	
	/**
	 * If there is only one unresolved cell in a row (column, box) where a certain value can be placed, place it there
	 * Calls colElimination, rowElimination, boxElimination
	 * @return true if any of the elimination methods return true
	 */
	private boolean elimination(){
		boolean colElimination = colElimination();
		boolean rowElimination = rowElimination();
		boolean boxElimination = boxElimination();
		boolean elimination = colElimination | rowElimination | boxElimination;
		
		return elimination;
	}
	
	/**
	 * If there is only one unresolved cell in a column where a certain value can be placed, place it there
	 * @return true if a value is placed, false otherwise
	 */
	private boolean colElimination(){
		boolean colElimination = false;

		//for each value
		for(int value = 1; value<=sudokuBoard.getBoardSize(); value++){
			//for each column
			for(int col = 0; col<sudokuBoard.getBoardSize(); col++){
				// count of cells that can hold value
				int valCount = 0;
				// cell that can hold value
				Cell valHoldingCell = null;
				// row the matching cell lives in
				int matchingRow = -1;
				
				//for each row in column
				for(int row = 0; row<sudokuBoard.getBoardSize(); row++){
					//keep track of count of cells that can hold the value
					if(!sudokuBoard.getCell(row, col).isSolved()){
						if(sudokuBoard.getCell(row, col).containsPossibleValue(value)){
							valCount++;
							valHoldingCell = sudokuBoard.getCell(row, col);
							matchingRow = row;
						}
					}
				}
				//if only one cell can hold the value, place it and set colElimination to true
				if(valCount == 1){
					sudokuBoard.placeCell(valHoldingCell, matchingRow, col, value);
					colElimination = true;
				}
			}
		}
	
		return colElimination;
	}
	
	/**
	 * If there is only one unresolved cell in a row where a certain value can be placed, place it there
	 * @return true if a value is placed, false otherwise
	 * See comments in colElimination if strategy is unclear
	 */
	private boolean rowElimination(){
		boolean rowElimination = false;

		//for each value
		for(int value = 1; value<=sudokuBoard.getBoardSize(); value++){
			//for each row
			for(int row = 0; row<sudokuBoard.getBoardSize(); row++){
				int valCount = 0;
				Cell valHoldingCell = null;
				int matchingCol = -1;
				//for each column in row
				for(int col = 0; col<sudokuBoard.getBoardSize(); col++){
					//keep track of count for
					if(!sudokuBoard.getCell(row, col).isSolved()){
						if(sudokuBoard.getCell(row, col).containsPossibleValue(value)){
							valCount++;
							valHoldingCell = sudokuBoard.getCell(row, col);
							matchingCol = col;
						}
					}
				}
				if(valCount == 1){
					sudokuBoard.placeCell(valHoldingCell, row, matchingCol, value);
					rowElimination = true;
				}
			}	
		}
		
		return rowElimination;
	}
	
	/**
	 * If there is only one unresolved cell in a box where a certain value can be placed, place it there
	 * @return true if a value is placed, false otherwise
	 * See comments in colElimination if strategy is unclear
	 */
	private boolean boxElimination(){
		boolean boxElimination = false;
		int boardSize = sudokuBoard.getBoardSize();
		//board is numberBoxes x numberBoxes big (in boxes
		int numberBoxes =  boardSize/(int) (Math.sqrt(boardSize));
		//for each value
		for(int value=1; value<=boardSize; value++){
			//for each box
			for(int boxRow = 0; boxRow<numberBoxes; boxRow++){
				for(int boxCol = 0; boxCol<numberBoxes; boxCol++){
					int rowStart = boxRow * (int) (Math.sqrt(boardSize));
					int colStart = boxCol * (int) (Math.sqrt(boardSize));
					int rowEnd = rowStart + (int) (Math.sqrt(boardSize)) - 1;
					int colEnd = colStart + (int) (Math.sqrt(boardSize)) - 1;
					
					int valPosCount = 0;
					Cell valHoldingCell = null;
					int matchingCol = -1;
					int matchingRow = -1;
					//for each cell in the box
					for(int row=rowStart; row<=rowEnd; row++){
						for(int col=colStart; col<=colEnd; col++){
							//keep track of count for
							if(!sudokuBoard.getCell(row, col).isSolved()){
								if(sudokuBoard.getCell(row, col).containsPossibleValue(value)){
									valPosCount++;
									valHoldingCell = sudokuBoard.getCell(row, col);
									matchingCol = col;
									matchingRow = row;
								}
							}
						}
					}
			
					if(valPosCount == 1){
						sudokuBoard.placeCell(valHoldingCell, matchingRow, matchingCol, value);
						boxElimination = true;
					}
				}
			}
		}
		
		return boxElimination;
	}
	
	/**
	 * If two cells in a row (column, box) have two candidates a and b, a and b can be removed from all other cells in the row (column, box).
	 * Calls colElimination, rowElimination, boxElimination 
	 * @return true if any of the called methods return true
	 */
	private boolean pairElimination(){
		boolean colElim = pairEliminationColumns();
		boolean rowElim = pairEliminationRows();
		boolean boxElim = pairEliminationBoxes();
	
		boolean pairElim = colElim | rowElim |  boxElim;
		
		return pairElim;
	}
	
	/**
	 * If two cells in a column have two candidates a and b, a and b can be removed from all other cells in the column.
	 * @return true if a pair is found
	 */
	private boolean pairEliminationColumns(){
		boolean pairEliminated = false;
		//for each column
		for(int col=0; col<sudokuBoard.getBoardSize(); col++){
			//for each row in the column
			for(int row=0; row<sudokuBoard.getBoardSize(); row++){
				//if the cell is unsolved and has only two possibilities
				if(!sudokuBoard.getCell(row, col).isSolved() && sudokuBoard.getCell(row, col).getPossibleValuesCount() ==2){
					Object[] possibleValues = sudokuBoard.getCell(row, col).getPossibleValues();
					// for each other row in column
					// determine if any other boxes have the same two candidates
					for(int row2=row+1; row2<sudokuBoard.getBoardSize(); row2++){
						if(!sudokuBoard.getCell(row2, col).isSolved()){
								Object[] possibleValues2 = sudokuBoard.getCell(row2, col).getPossibleValues();
								boolean match = true;
								//determine if possibleValues.equals(possibleValues2)
								//TODO: extract this method (called 3 times in different pairElim methods)
								for(int possibleValue = 0; possibleValue<possibleValues.length; possibleValue++){
									if(!possibleValues[possibleValue].equals(possibleValues2[possibleValue])){
										match = false;
									}
								}

								if(match){
									//get two possible values
									int firstValue = 0;
									int secondValue = 0;
									for(int possibleValue = 0; possibleValue<possibleValues.length; possibleValue++){
										if(!possibleValues[possibleValue].equals(" ")){
											if(firstValue==0){
												firstValue = (Integer) possibleValues[possibleValue];
											}
											else secondValue = (Integer) possibleValues[possibleValue];
										}
									}
									//remove from all other column positions
									sudokuBoard.removeColPossibilities(firstValue, col, row, row2);
									sudokuBoard.removeColPossibilities(secondValue, col, row, row2);
									pairEliminated = true;
								}
							}
					}
				}
			}
			
		}
		return pairEliminated;
	}

	/**
	 * If two cells in a row have two candidates a and b, a and b can be removed from all other cells in the row.
	 * @return true if a pair is found
	 */
	private boolean pairEliminationRows(){
		boolean pairEliminated = false;
		//for each row
		for(int row=0; row<sudokuBoard.getBoardSize(); row++){
			//for each column in the row
			for(int col=0; col<sudokuBoard.getBoardSize(); col++){
				// if cell is unsolved and has only two possible values
				if(!sudokuBoard.getCell(row, col).isSolved()  && sudokuBoard.getCell(row, col).getPossibleValuesCount() == 2){
					Object[] possibleValues = sudokuBoard.getCell(row, col).getPossibleValues();
					// for each other column in row
					// determine if any two boxes have the same two candidates
					for(int col2=col+1; col2<sudokuBoard.getBoardSize(); col2++){
						if(!sudokuBoard.getCell(row, col2).isSolved()){
								Object[] possibleValues2 = sudokuBoard.getCell(row, col2).getPossibleValues();
								boolean match = true;
								//determine if possibleValues.equals(possibleValues2)
								for(int possibleValue = 0; possibleValue<possibleValues.length; possibleValue++){
									if(!possibleValues[possibleValue].equals(possibleValues2[possibleValue])){
										match = false;
									}
								}

								if(match){
									//get two possible values
									int firstValue = 0;
									int secondValue = 0;
									for(int possibleValue = 0; possibleValue<possibleValues.length; possibleValue++){
										if(!possibleValues[possibleValue].equals(" ")){
											if(firstValue==0){
												firstValue = (Integer) possibleValues[possibleValue];
											}
											else secondValue = (Integer) possibleValues[possibleValue];
										}
									}
									//remove from all other rows
									sudokuBoard.removeRowPossibilities(firstValue, row, col, col2);
									sudokuBoard.removeRowPossibilities(secondValue, row, col, col2);
								}
							}
						}
					}
				}
			}
			return pairEliminated;
		}
		
	/**
	 * If two cells in a box have two candidates a and b, a and b can be removed from all other cells in the box.
	 * @return true if a pair is found
	 */
		private boolean pairEliminationBoxes(){
			boolean pairEliminated = false;
			int boardSize = sudokuBoard.getBoardSize();
			//board is numberBoxes x numberBoxes big (in boxes)
			int numberBoxes =  boardSize/(int) (Math.sqrt(boardSize));
			//for each box (boxRow and boxCol loops used to figure out rowStart/colStart and rowEnd/colEnd)
			for(int boxRow = 0; boxRow<numberBoxes; boxRow++){
				for(int boxCol = 0; boxCol<numberBoxes; boxCol++){
					// set box rowStart, rowEnd, colStart, colEnd
					int rowStart = boxRow * (int) (Math.sqrt(boardSize));
					int colStart = boxCol * (int) (Math.sqrt(boardSize));
					int rowEnd = rowStart + (int) (Math.sqrt(boardSize)) - 1;
					int colEnd = colStart + (int) (Math.sqrt(boardSize)) - 1;
					// logic to check for pairs in each cell of box
					for(int row = rowStart; row<=rowEnd; row++){
						for(int col = colStart; col<=colEnd; col++){
							//if cell is unsolved and has only two possible values
							if(!sudokuBoard.getCell(row, col).isSolved()  && sudokuBoard.getCell(row, col).getPossibleValuesCount() == 2){
								//currentCell Values
								Object[] possibleValues = sudokuBoard.getCell(row, col).getPossibleValues();
								//check all other cells in box
								//TODO: figure out a better strategy not to do multiple checks but also not to miss any (this checks same cells multiple times)
								for(int row2 = row; row2<=rowEnd; row2++){
									for(int col2 = col; col2<=colEnd; col2++){
										if(!sudokuBoard.getCell(row2, col2).isSolved() && !(row==row2 && col==col2)){											
											Object[] possibleValues2  = sudokuBoard.getCell(row2, col2).getPossibleValues();
											
											boolean match = true;
											//determine if possibleValues.equals(possibleValues2)
											for(int possibleValue = 0; possibleValue<possibleValues.length; possibleValue++){
												if(!possibleValues[possibleValue].equals(possibleValues2[possibleValue])){
													match = false;
												}
											}
											
											if(match){
												//get two possible values
												int firstValue = 0;
												int secondValue = 0;
												for(int possibleValue = 0; possibleValue<possibleValues.length; possibleValue++){
													if(!possibleValues[possibleValue].equals(" ")){
														if(firstValue==0){
															firstValue = (Integer) possibleValues[possibleValue];
														}
														else secondValue = (Integer) possibleValues[possibleValue];
													}
												}
												//remove value from all other cells in box
												sudokuBoard.removeBoxPossibilities(firstValue, row, row2, col, col2, rowStart, rowEnd, colStart, colEnd);
												sudokuBoard.removeBoxPossibilities(secondValue, row, row2, col, col2, rowStart, rowEnd, colStart, colEnd);												
											}
										}
									}
								}									
							}
						}
					}					
				}
			}
			
			return pairEliminated;
		}
		
		/**
		 * if a number only occurs in one box in a column, eliminate the number from the other columns in the box
		 * @return true if a value is eliminated
		 */
		public boolean colBox(){
			boolean colBox = false;
			int boardSize = sudokuBoard.getBoardSize();
			//for each column
			for(int col=0; col<boardSize; col++){
				//for each value
				for(int value=1; value<=boardSize; value++){
					//board is numberBoxes x numberBoxes big (in boxes)
					int numberBoxes =  boardSize/(int) (Math.sqrt(boardSize));
					int matchingBoxes = 0;
					int matchingBox = -1;
					int matchingCol = -1;
					//for each box, determine if value exists in that cell (for the current col)
					for(int box = 0; box<numberBoxes; box++){
						//set rowStart, rowEnd, initialize matchingCells
						int rowStart = box * (int) (Math.sqrt(boardSize));
						int rowEnd = rowStart + (int) (Math.sqrt(boardSize)) - 1;
						int matchingCells = 0;
						
						//for each row in the cell, check for value, increment matchingCells if found
						for(int row=rowStart; row<=rowEnd; row++){
							if(!sudokuBoard.getCell(row, col).isSolved()){
								if(sudokuBoard.getCell(row, col).containsPossibleValue(value)){
									matchingCells++;
								}
							}
						}
						
						//if value exists in this box, increment matchingBoxes and set matchingBox, matchingCol
						if(matchingCells > 0){
							matchingBoxes++;
							matchingBox = box;
							matchingCol = col;
						}
					}
					// if there is only one box with the value for this column, remove from other column in the box
					if(matchingBoxes == 1){
						sudokuBoard.removeBoxColPossibilities(matchingBox, matchingCol, value);
					}
				}
			}
			return colBox;
		}
		
		/**
		 * if a number only occurs in one box in a row, eliminate the number from the other rows in the box
		 * @return true if a value is eliminated
		 * See colBox for more comments if strategy is unclear
		 */
		private boolean rowBox(){
			boolean rowBox = false;
			int boardSize = sudokuBoard.getBoardSize();
			//for each row
			for(int row=0; row<boardSize; row++){
				//for each value
				for(int value=1; value<=boardSize; value++){
					//board is numberBoxes x numberBoxes big (in boxes
					int numberBoxes =  boardSize/(int) (Math.sqrt(boardSize));
					int matchingBoxes = 0;
					int matchingBox = -1;
					int matchingRow = -1;
					//for each box
					for(int box = 0; box<numberBoxes; box++){
						int colStart = box * (int) (Math.sqrt(boardSize));
						int colEnd = colStart + (int) (Math.sqrt(boardSize)) - 1;
						int matchingCells = 0;
						
						for(int col=colStart; col<=colEnd; col++){
							if(!sudokuBoard.getCell(row, col).isSolved()){
								if(sudokuBoard.getCell(row, col).containsPossibleValue(value)){
									matchingCells++;
								}
							}
						}
						if(matchingCells > 0){
							matchingBoxes++;
							matchingBox = box;
							matchingRow = row;
						}
					}
					if(matchingBoxes == 1){
						//remove from other rows in the box
						sudokuBoard.removeBoxRowPossibilities(matchingBox, matchingRow, value);
					}
				}
			}

			return rowBox;
		}	
		
}
